package practise.alogrithm.hundredInterviewQuestions.convertToConcurrent;

import practise.alogrithm.hundredInterviewQuestions.Utils.TreeBuilder;
import practise.alogrithm.hundredInterviewQuestions.Utils.TreeNode;

import java.util.concurrent.*;

/**
 * Created by richard on 6/16/14.
 */
public class CommonNodeInTree extends RecursiveTask<TreeNode> {
    private TreeNode treeNode,node1,node2;

    public CommonNodeInTree(TreeNode treeNode, TreeNode node1, TreeNode node2) {
        this.treeNode = treeNode;
        this.node1 = node1;
        this.node2 = node2;
    }

    @Override
    protected TreeNode compute() {
        if(treeNode==null){
            return null;
        }
        if(treeNode.getValue() == node1.getValue() || treeNode.getValue() == node2.getValue()){
            return treeNode;
        }
        CommonNodeInTree forLeft = new CommonNodeInTree(treeNode.getLeft(),node1,node2);
        CommonNodeInTree forRight = new CommonNodeInTree(treeNode.getRight(),node1,node2);
        forLeft.fork();
        forRight.fork();
        TreeNode left = forLeft.join();
        TreeNode right = forRight.join();
        if(left!=null && right!=null){
            return treeNode;
        }
        if(left!=null){
            return left;
        }
        if(right!=null){
            return right;
        }
        return null;
    }

    public static void main(String[] args) throws ExecutionException, InterruptedException {
        CommonNodeInTree commonNodeInTree = new CommonNodeInTree(
                TreeBuilder.createTreeByArrayInWidth(new int[]{1, 2, 3, 4, 5, 6, 7}), new TreeNode(4),new TreeNode(7));
        ForkJoinPool forkJoinPool = new ForkJoinPool();
        Future<TreeNode> future =  forkJoinPool.submit(commonNodeInTree);
        forkJoinPool.awaitQuiescence(1000, TimeUnit.SECONDS);
        System.out.println("Result:"+future.get().getValue());
    }
}
